package com.gemini.main.sort;

public class Sqr {

    // 牛顿迭代公式求平方根
    //xi+1=xi - f(xi) / f'(xi)
    //xi+1=xi - (xi2 - n) / (2xi) = xi - xi / 2 + n / (2xi) = xi / 2 + n / 2xi = (xi + n/xi) / 2
    public static double SQR(int n) {
        double x1 = 1, x2;
        x2 = x1 / 2.0 + n / (2 * x1);
        while (Math.abs(x2 - x1) > 0.0001) {
            x1 = x2;
            x2 = x1 / 2.0 + n / (2 * x1);
        }
        return x2;
    }

    //二分查找
    public static double SQR1(int num, double low, double high, double range) {
        double mid = (low + high) / 2f;
        if (num - mid * mid < 0) {
            return SQR1(num, low, (mid + high) / 2f, range);
        } else {
            if (num - mid * mid > range) {
                return SQR1(num, (low + mid) / 2f, high, range);
            }
            String str = String.format("%.6f", mid);
            return Double.valueOf(str);
        }

    }

    public static void main(String[] args) {
        System.out.println(SQR(3));
    }
}
